package com.major.sort.insertsorting;

public class InsertSort {
    public static void insertSort(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];         // 提前保存插入值
            int frontIndex = i - 1;         // 从被插入的第一个下标开始比较
            //       ↑  数组下标越界            ↑ 比较插入值和前一个数的大小
            while (frontIndex >= 0 && insertVal < arr[frontIndex]) {
                arr[frontIndex + 1] = arr[frontIndex];      // 前一个值依次往后覆盖，插入值已经提前保存
                frontIndex--;       // 如果比前一个小，继续往前比
            }
            //if (frontIndex + 1 != i) {
            //}
            arr[frontIndex + 1] = insertVal;    // 上面frontIndex多减了一次，这里加上
        }
    }
}
